package stu.day48;

public class MagicDictionary {
    class Treenode{
        boolean flag = false;
       Treenode[] children = new Treenode[26];
    }

    Treenode root ;

    public MagicDictionary() {
        root = new Treenode();
    }

    public void buildDict(String[] dictionary) {
        for (String word:dictionary){
            Treenode node = root;
            for(char ch:word.toCharArray()){
                int num = ch-'a';
                if(node.children[num]==null){
                    node.children[num]=new Treenode();
                }
                node = node.children[num];
            }
            node.flag=true;
        }
    }

    public boolean search(String searchWord) {

        return dfs(searchWord,root,0,true);

    }

    public boolean dfs(String searchWord,Treenode node,int l,boolean use){

        if(node==null){
            return false;
        }

        if(l==searchWord.length()  && !use){
            return node.flag;
        }


        int num = searchWord.charAt(l) - 'a';

        for (int i=0;i<26;i++){
            if(i==num && node.children[i]!=null && dfs(searchWord,node.children[i],l+1,use)){
                return true;

            } else if(i!=num && node.children[i]!=null && use && dfs(searchWord,node.children[i],l+1,false)){
                return true;

            }
        }

        return false;

    }


}
